package 全排列;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author: AirMan
 * @date: 2025/4/17 10:30
 * @description: 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
 * 示例:
 * 输入: [1,2,3]
 * 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
 */
public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        // 全排列问题 ==> 回溯法
        // 回溯的参数；nums, result, path, used
        // 回溯的返回值：void
        // 回溯的终止条件：path.length == nums.length
        // 单层回溯的逻辑：
        // 横向遍历需要从 0 到 nums 的末尾，因为全排列需要考虑到每一个元素。
        // 纵向遍历就是确定了一个元素的选择，也就是在确定分支是从根节点到叶子节点的路径
        // 我们需要保证元素的选择不能重复，也就需要定义一个 used 数组用来记录一条路径是否选择了某一个元素

        used = new boolean[nums.length];
        backtracking(nums);
        return result;
    }

    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    boolean[] used;

    public void backtracking(int[] nums) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            backtracking(nums);
            used[i] = false;
            path.removeLast();
        }
    }
}
